package william.array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * @author ZhangShenao
 * @date 2024/3/6
 * @description <a href="https://leetcode.cn/problems/3sum/description/">...</a>
 */
public class Leetcode15_三数之和 {
    /**
     * 采用排序+指针碰撞法
     * 首先将数组排好序
     * 然后遍历数组,针对每一个元素,在后面通过指针对撞法,找到2个元素,使得3个数和==0
     * 因为不可以包含重复的三元组,因此遇到重复元素要跳过
     * <p>
     * 时间复杂度: 排序O(N*logN)+指针碰撞遍历O(N^N) = O(N^N)
     * 空间复杂度O(1)
     */
    public List<List<Integer>> threeSum(int[] nums) {
        //边界条件校验
        if (nums == null || nums.length < 3) {
            return Collections.emptyList();
        }

        int N = nums.length;
        List<List<Integer>> result = new ArrayList<>();

        //将数组排好序
        Arrays.sort(nums);

        //遍历数组,通过指针对撞法,找到3数之和
        for (int i = 0; i < N - 2; i++) {
            if (nums[i] > 0) {   //因为数组是有序的,如果当前元素已经>0,则一定无结果,直接返回
                return result;
            }

            if (i > 0 && nums[i] == nums[i - 1]) {   //跳过重复元素
                continue;
            }

            //通过指针对撞法,在后面找到2个元素,使得这3个数的和为0
            int target = -nums[i];
            int l = i + 1;
            int r = N - 1;
            while (l < r) {
                int sum = nums[l] + nums[r];
                if (sum > target) {
                    r--;
                    continue;
                }
                if (sum < target) {
                    l++;
                    continue;
                }

                //找到一组目标三元组,保存到结果中
                List<Integer> triple = new ArrayList<>();
                triple.add(nums[i]);
                triple.add(nums[l]);
                triple.add(nums[r]);
                result.add(triple);

                //跳过重复元素,继续寻找下一组
                while (l < r && nums[l] == nums[l + 1]) {
                    l++;
                }
                while (r > l && nums[r] == nums[r - 1]) {
                    r--;
                }
                l++;
                r--;
            }
        }


        //返回结果
        return result;
    }
}
